package week_04;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class LowestCommonAncestor_236 {

    private Map<TreeNode, TreeNode> parents = new HashMap<>();
    private List<TreeNode> reds = new ArrayList<>();

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 遍历存储子到父的映射
        dfs(root);
        reds.add(root);
        // 从p开始向上标红node
        while (p != root) {
            reds.add(p);
            //if (!parents.containsKey(parent)) break;
            p = parents.get(p);
        }
        // 从q向上寻找第一个标红的点
        while (q != root) {
            if (reds.contains(q)) break;
            q = parents.get(q);
        }
        return q;
    }


    public void dfs(TreeNode root) {
        if (root == null) return;
        if (root.left != null) {
            parents.put(root.left, root);
        }

        if (root.right != null) {
            parents.put(root.right, root);
        }
        dfs(root.left);
        dfs(root.right);
    }
}
